/*
 * @lc app=leetcode.cn id=307 lang=typescript
 *
 * [307] 区域和检索 - 数组可修改
 */

// @lc code=start

class FenwickTree {
  data: number[];
  n: number;
  constructor(n: number) {
    this.n = n;
    this.data = new Array(n + 1).fill(0);
  }
  _lowbit(x: number) {
    return x & -x;
  }
  update(i: number, val: number) {
    while (i <= this.n) {
      this.data[i] += val;
      i += this._lowbit(i);
    }
  }
  query(i: number) {
    let sum = 0;
    while (i > 0) {
      sum += this.data[i];
      i -= this._lowbit(i);
    }
    return sum;
  }
  at(i: number) {
    return this.query(i) - this.query(i - 1);
  }
}

class NumArray {
  fenwickTree: FenwickTree;
  constructor(nums: number[]) {
    this.fenwickTree = new FenwickTree(nums.length);
    for (let i = 0; i < nums.length; i++) {
      this.fenwickTree.update(i + 1, nums[i]);
    }
  }

  update(index: number, val: number): void {
    this.fenwickTree.update(index + 1, val - this.fenwickTree.at(index + 1));
  }

  sumRange(left: number, right: number): number {
    return this.fenwickTree.query(right + 1) - this.fenwickTree.query(left);
  }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * obj.update(index,val)
 * var param_2 = obj.sumRange(left,right)
 */
// @lc code=end
